//

#include <stdio.h>

int quick_pow(int a, int b, int c) {
    int res = 1 % c;
    while (b) {
        if (b & 1) {
            res = (long long) (res * a % c);
        }
        b >>= 1;
        a = (long long) (a * a % c);
    }
    return res;
}



int main() {
    int n, a, b, c;
    scanf("%d", &n);
    while (n-->0) {
        scanf("%d%d%d", &a, &b, &c);
        printf("%d\n", quick_pow(a, b, c));
    }
    return 0;
}